# 步骤：
# 1.假设第一个元素为最小，记录索引位置为0
# 2.遍历下标1到n-1的元素，找到其中最小的元素进行交换
# 3.这样第一个元素为最小，又假设第二个元素为最小,记录索引位置1
# 4.遍历索引位置2到n-1，找到最小值和索引位置1的元素交换
# 5.以次类推，重复上述3,4步骤

def selection_sort(arr):
    n = len(arr)

    for j in range(n-1):
        min_index = j
        # j = 0 时找到索引1到n-1最小的元素进行交换
        # j = 1 时找到索引2到n-2最小的元素进行交换
        # j = 2 时,以此类推
        for i in range(j+1, n):
            if arr[i] < arr[min_index]:
                min_index = i
        arr[min_index], arr[j] = arr[j], arr[min_index]
            


if __name__ == '__main__':
    arr = [3, 1, 2, 5, 4]
    selection_sort(arr)
    print(arr)
    assert arr == [1, 2, 3, 4, 5]